#include "linearList.h"
#include <iostream>
using namespace std;

//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for(int i = 0; i < curNumberOfItem-1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem-1] << endl;
}



//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while(curNode != lastNode)
    {
        if(curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }
        
        
        curNode = curNode->next;
    }
}

sequenceList::sequenceList(const int& maxsize, const int& initsize, float list[] ){
    if(!(maxsize > 0 && initsize >=0)) {
        myList = nullptr;
        curNumberOfItem = 0;
        maxCapcity = 0;
        return;//错误
    }

    if(initsize > maxsize){
        myList = nullptr;
        curNumberOfItem = 0;
        maxCapcity = 0;
        return;
    }//处理错误

    maxCapcity = maxsize;
    curNumberOfItem = initsize;
    
    myList = new float[maxCapcity];

    int i = 0;
    if(initsize != 0){
        
        for(i; i< initsize; i++)
        {
            myList[i] = list[i];
        }//诶个赋值
    }
    return;
    
}

sequenceList::~sequenceList(){
    delete[] myList;
    return;
}

bool sequenceList::addItem(const float& New){
    if(curNumberOfItem >= maxCapcity){
        return false;
    }
    myList[curNumberOfItem] = New;
    curNumberOfItem++;//别忘了更新
    return true;
}

bool sequenceList::insertItem(const int& index ,const float& num){
    if(curNumberOfItem >= maxCapcity || index > curNumberOfItem  || index < 0){//错误的索引
        return false;
    }
    int i = curNumberOfItem;
    for(i; i >index; --i){
        myList[i] = myList[i-1];
    }
    myList[index] = num;
    curNumberOfItem++;
    return true;
}

int sequenceList::deleteItem(const float& num){
    int i = 0, j = 0;
    for(i; i < curNumberOfItem ;i++){
        if(myList[i] == num ){
            j++;
            break;//记录索引
        }
    }
    if(j && i < curNumberOfItem){
        int k = i;
        for(k; k < curNumberOfItem - 1; k++){
            myList[k] = myList[k+1];//补位
        }
        curNumberOfItem--;
        return i;
    }
    else{return -1;}
}
bool sequenceList::locate(const int& index, float&val){
    if(index > (curNumberOfItem - 1) || index < 0){
        return false;
    }
    else{
        val = myList[index];
    }
    return true;
}

int sequenceList::locate(const float& num){
    if(curNumberOfItem == 0 ){return -1;}
    int i = 0;
    for(i ; i < curNumberOfItem; i++){
        if(myList[i] == num){return i;}
    }
    return -1;
}

void sequenceList::reverse(){
    if(curNumberOfItem == 0 ){return;}
    int i = 0;
    for(i; i < (curNumberOfItem/2) ; i++){
        float temp = myList[i];
        myList[i] = myList[curNumberOfItem - 1 - i];//头和尾换，折中
        myList[curNumberOfItem - 1 - i] = temp;
    }
    return;
}

listNode::listNode(float nodeData, listNode* succ){
    data = nodeData;
    next = succ;
}
listNode::~listNode(){
    next = nullptr;
}
linkList::linkList(){
    firstNode = new listNode();
    curNode = firstNode;
    lastNode = firstNode;
    listSize = 0;
}
linkList::linkList(const int& len, float a[]){
    firstNode = new listNode();
    curNode = firstNode;
    lastNode = firstNode;
    listSize = 0;//至少留一个空表头
    int i = 0;
    for(i; i < len ; i++){
        listNode *newnode = new listNode(a[i]);
        
        if(newnode == nullptr){
            break;//呃，内存不足
        }

            lastNode ->next = newnode;
            lastNode = newnode;
        

        listSize++;
    }

    
}

linkList::~linkList(){
    listNode *temp;
    while(firstNode != NULL){
        temp = firstNode;
        firstNode = firstNode ->next;
        delete temp;
    }
    firstNode = nullptr;
    curNode = nullptr;
    lastNode = nullptr;
    listSize = 0;
}

bool linkList::headInsertItem(const float& n){
    listNode *newnode = new listNode(n);
    if(newnode == nullptr){ return false;}
    newnode ->next = firstNode ->next;//保持头结点不存值
    firstNode->next = newnode;
    if (listSize == 0) {
        lastNode = newnode;//更新尾节点
    }
    listSize++;
    return true;
}

bool linkList::tailInsertItem(const float& n){
    listNode *newnode = new listNode(n);
    if(newnode == nullptr){ return false;}
    lastNode ->next = newnode;
    lastNode = newnode;
    listSize++;
    return true;
}

int linkList::insertItem(const int& i,const float& n){
    if(i >= listSize || i <0){return -1;}
    listNode *newnode = new listNode(n);
    curNode = firstNode;
    int j = 0;
    for(j; j < i ; j++){//定位前一个
        curNode = curNode ->next;
    }
    newnode ->next = curNode ->next;
    curNode ->next = newnode;
    if(i == listSize-1){
        lastNode = lastNode ->next;//更新尾节点
    }
    listSize++;
    return i;
}

int linkList::deleteItem(const float& p){
    int i =0;
    int find = 0;
    curNode = firstNode;
    listNode * t = curNode ->next;
    for(i; i < listSize; i++){
        if(p == t ->data){
            find++;
            break;
        }
        curNode = curNode ->next;
        t = t ->next;
    }
    if(find){//cur存着前一个,t存要删的
        curNode ->next = t ->next;
        delete t;

        if(i == listSize-1){
            lastNode = curNode;
        }

        listSize--;
        return i;
    }


    return -1;


}



bool linkList::locate(const int& i, float& val){
    if(i >= listSize || i <0){return false;}//空表
    curNode = firstNode ->next;
    int j = 0;
    for(j; j < i ; j++){
        curNode = curNode ->next;
    }

    val = curNode ->data;
    return true;
}

int linkList::locate(const float& p){
    int j = 0;
    curNode = firstNode ->next;
    int f = 0;
    for(j; j < listSize ; j++){
        if(p == curNode ->data){
            
            return j;    
        }
        curNode = curNode ->next;
    }
    return -1;

}


void linkList::ascendingOrder(){
    if(listSize <= 1){return;}
    listNode *yipai = firstNode ->next;//已排序的开头
    listNode *weipai = yipai ->next;//未排序的开头
    yipai ->next =nullptr;//断！
    while(weipai)
    {
        curNode = weipai;//取一个未排的
        weipai = weipai ->next;
        if(yipai ->data >= curNode ->data)
        {//如果小于最小的
            curNode ->next = yipai;
            yipai = curNode;
        }
        else
        {//一般情况
            listNode *p = yipai;//存前一个
            while(p->next != nullptr//防止访问nullptr 
                && p ->next->data < curNode ->data){
                p = p ->next;//找
                }
            curNode ->next = p ->next;
            p ->next = curNode;
        }
    }
    firstNode ->next = yipai;
    lastNode = firstNode;
    while (lastNode ->next != nullptr){lastNode = lastNode ->next;}
}

void linkList::reverse(){
    if(listSize <= 1){return;}

    curNode = firstNode ->next;
    listNode *pre = nullptr;
    listNode *next = nullptr;

    firstNode ->next = lastNode;//反转

    lastNode = curNode;

    while (curNode)
    {
        next = curNode ->next;//存档
        curNode ->next = pre;//反转
        pre = curNode;
        curNode = next;//一个一个反转

    }

    lastNode ->next = nullptr;


}

void merge(linkList& a, linkList& b){
    
    
    int bi = 0;
    float bv;

    while(b.locate(bi , bv)){
        a.tailInsertItem(bv);
        bi++;//一个一个接
    }

    b.~linkList();//删掉b

    a.ascendingOrder();
    a.reverse();
    
    
    
    
}